package se.kth.fericss.quicksort;
public class QuicksortRandomPivotInsertionsort implements Quicksorter {
	public int k;
	public QuicksortRandomPivotInsertionsort(){
		k=20;
	}
	public QuicksortRandomPivotInsertionsort(int k){
		this.k=k;
	}
	@Override
	public void sort(int[] v, int low, int high) {
		if(check.checkSpecial(v, low, high))
			return;
		helpSort(v, low, high);	
	}
	@Override
	public void helpSort(int[] v, int low, int high) {
		if(high-low<=k){
			//break the recursion if the partition is less then k elements
			//and finish the rest with insertionSort
			Quicksorter.ins.sort(v,low,high);
		}
		else{
			//  l is the lower index, h is the upper index
			//  of the region of array a that is to be sorted
		    int l=low, h=high, t; //t is a temporary variable
		    // Choose a random pivot element.
		    int p=v[(int)(rnd.nextInt(h-l)+l)];
		    //  partition
		    while (l<=h)
		    {   
		        while (v[l]<p) //search for elements bigger then the pivot
		        	l++; 
		        while (v[h]>p) //search for elements smaller then the pivot
		        	h--; 
		        if (l<=h) //swap the elements & increase low & decrease high
		        {
		            t=v[l]; 
		            v[l]=v[h];
		            v[h]=t;
		            l++; 
		            h--;
		        }
		    }
		    //  recursion
		    if (low<h) {helpSort(v, low, h);}
		    if (l<high){helpSort(v, l, high);}
		}
	}
	@Override
	public String getType() {
		return "Random pivot element with insertionsort";
	}
}